package com.kds.changzhou;

/**
 * @author 孔德嵩
 * 创建日期 2024/10/13
 */
import java.util.ArrayList;
import java.util.List;

public class Permutation {

    public static void main(String[] args) {
        String str = "abc"; // 输入字符串
        List<String> result = permute(str);
        System.out.println("所有变位字:");
        for (String s : result) {
            System.out.println(s);
        }
    }

    // 生成字符串的所有变位字
    public static List<String> permute(String str) {
        List<String> results = new ArrayList<>();
        boolean[] used = new boolean[str.length()];
        backtrack(new StringBuilder(), str, used, results);
        return results;
    }

    // 回溯方法
    private static void backtrack(StringBuilder path, String str, boolean[] used, List<String> results) {
        // 如果路径的长度与输入字符串的长度相等，则找到了一个排列
        if (path.length() == str.length()) {
            results.add(path.toString());
            return;
        }
        // 遍历每个字符，尝试将其加入路径中
        for (int i = 0; i < str.length(); i++) {
            if (used[i]) {
                continue; // 如果字符已经使用，则跳过
            }
            // 将字符添加到路径中
            path.append(str.charAt(i));
            used[i] = true; // 标记字符为已使用
            // 递归调用
            backtrack(path, str, used, results);
            // 回溯，移除最后一个字符并标记为未使用
            path.deleteCharAt(path.length() - 1);
            used[i] = false;
        }
    }
}
